import java.util.Stack;

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        MyLinkedList myLinkedList1 = new MyLinkedList();
        MyLinkedList myLinkedList2 = new MyLinkedList();
        //myLinkedList.addFirst(4);
        //myLinkedList.addFirst(2);
        //myLinkedList.addFirst(1);
        myLinkedList1.addFirst(4);
        myLinkedList1.addFirst(3);
        myLinkedList1.addFirst(1);
        myLinkedList.display();
        myLinkedList1.display();
        myLinkedList2.head =  mergeTwoLists(myLinkedList.head,myLinkedList1.head);
        myLinkedList2.display();

        //myLinkedList.head = partition(myLinkedList.head,2);
        //myLinkedList.display();
    }
    ///*合并两个有序链表*/
    public static MyLinkedList.ListNode mergeTwoLists(MyLinkedList.ListNode list1, MyLinkedList.ListNode list2) {
        if (null == list1) {
            return list2;
        }
        if (null == list2) {
            return list1;
        }
        // 遍历两个链表，将较小的节点往新链表中尾插
        // 为了实现方便，新链表使用带头节点的链表
        MyLinkedList.ListNode newHead = new MyLinkedList.ListNode(1);
        MyLinkedList.ListNode tail = newHead;
        MyLinkedList.ListNode cur1 = list1;
        MyLinkedList.ListNode cur2 = list2;
        // 只要两个链表都不为空，从前往后遍历
        // 将小的尾插到tail之后
        while (null != cur1 && null != cur2) {
            if (cur1.val <= cur2.val) {
                tail.next = cur1;
                cur1 = cur1.next;
            } else {
                tail.next = cur2;
                cur2 = cur2.next;
            }
            tail = tail.next;
        }
        // while结束之后，肯定有一个链表先走到末尾
        // 将另外一个不空的链表直接连接在tail之后
        if (null != cur1) {
            tail.next = cur1;
        } else {
            tail.next = cur2;
        }
        return newHead.next;
    }
        /*错误解法：在只传一个数据的情况下,这个while循环会进来, 然后会报错空指针异常,
         因为另一个链表为空
        if(list1 == null && list2 == null){
            return null;
        }
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        MyLinkedList.ListNode cur1 = list1;
        MyLinkedList.ListNode cur2 = list2;
        MyLinkedList.ListNode head = new MyLinkedList.ListNode(1);
        if(cur1.val == cur2.val){
            head = cur1;
            cur1 = cur1.next;
        }else if(cur1.val > cur2.val){
            head = cur2;
            cur2 = cur2.next;
        }else if(cur1.val < cur2.val){
            head = cur1;
            cur1 = cur1.next;
        }
        MyLinkedList.ListNode cur = head;
        while(cur1 != null || cur2 != null){
            if((cur1 != null && cur2 != null) && cur1.val == cur2.val){
                cur.next = cur1;
                cur1 = cur1.next;
                cur = cur.next;
            }else if(cur1 == null || cur1.val > cur2.val){
                cur.next = cur2;
                cur2 = cur2.next;
                cur = cur.next;
            }else if(cur2 == null || cur1.val < cur2.val){
                cur.next = cur1;
                cur1 = cur1.next;
                cur = cur.next;
            }
        }return head;*/


    /*链表分割题：
    现有一链表的头指针 ListNode* pHead，给一定值x，
    编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，
    返回重新排列后的链表的头指针。*/
    public static MyLinkedList.ListNode partition(MyLinkedList.ListNode pHead, int x) {
        if(pHead == null){
            return null;
        }
        Stack<Integer> stack = new Stack<>();
        MyLinkedList.ListNode cur = pHead;
        MyLinkedList.ListNode  prev = pHead;
        while(cur != null){
            if(cur.val < x){
                if(cur == pHead){
                    pHead = pHead.next;
                    stack.push(cur.val);
                    cur = cur.next;
                }else {
                    stack.push(cur.val);
                    prev.next = cur.next;
                    cur = cur.next;
                }
            }else {
                prev = cur;
                cur =cur.next;
            }
        }
        while(!stack.isEmpty()){
            MyLinkedList.ListNode cur2 = new MyLinkedList.ListNode(stack.pop());
            cur2.next = pHead;
            pHead = cur2;
        }
        return pHead;
    }
}
